package interview.tree;

/**
 * Created with IntelliJ IDEA.
 * Description: 创建树
 * User: xxm
 * Date: 2018-02-22
 * Time: 13:02
 */
public class TreeCreator {

    public TreeNode createSampleTree() {
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.setRight(new TreeNode('C'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }

    /**
     * 已知前序和中序遍历构造二叉树
     *
     * @param preOrder 前序
     * @param inOrder  中序
     * @return 后序
     */
    public TreeNode createTree(String preOrder, String inOrder) {
        if (preOrder.isEmpty()) {
            return null;
        }

        char rootValue = preOrder.charAt(0);
        int rootIndex = inOrder.indexOf(rootValue);
//        int leftLength = rootIndex;
        TreeNode root = new TreeNode(rootValue);
        root.setLeft(createTree(
                // substring 从1开始跳过根节点，到1+rootIndex为左子树
                preOrder.substring(1, 1 + rootIndex),
                // 根节点在中序遍历中的下标即为左子树长度
                inOrder.substring(0, rootIndex)));
        root.setRight(createTree(
                // 剩下的元素即为右子树
                preOrder.substring(1 + rootIndex),
                inOrder.substring(1 + rootIndex))
        );
        return root;
    }

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeTraversal traversal = new TreeTraversal();

        TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
        traversal.postOrder(tree);
        System.out.println();
        traversal.postOrder(creator.createTree("", ""));
        System.out.println();
        traversal.postOrder(creator.createTree("A", "A"));
        System.out.println();
        traversal.postOrder(creator.createTree("AB", "BA"));
    }
}